This invention relates to information storage and retrieval systems, and more particularly to means for decoding codewords for use in error detection and correction in such systems. Even more particularly, this invention relates to Reed-Solomon codes and related codes, and to improved methods for the decoding of such codes.
In a typical decoder, the coefficients of the syndrome polynomial, called frequency-domain syndromes, are first calculated by dividing the received codeword by each factor of the code generator polynomial. This process is hardware-intensive and/or time-consuming, depending on implementation.
It is possible to efficiently generate the coefficients of the remainder polynomial, called time-domain syndromes, by dividing the received codeword by the entire code generator polynomial. The time-domain syndromes contain the same information as the frequency-domain syndromes.
Methods of decoding using frequency-domain syndromes are known in the prior art, for example see Chapter 3 Practical Error Correction Design for Engineers by Neal Glover and Chapter 5 of Error-Correction Coding for Digital Communications by Clark and Cain. For cases of one error, two frequency-domain syndromes can be used to generate an error location and value, which are then checked with other frequency-domain syndromes using a "Newton's Identities" test. A similar procedure starting with four frequency-domain syndromes may be used to decode cases of two errors. The calculation of frequency-domain syndromes adds significant additional hardware and/or time delay to decoding of cases of one and two errors.
For cases of more than two errors, the frequency-domain syndromes are typically used to iteratively generate an error locator polynomial and an error evaluator polynomial. The error locator polynomial is typically used in a "Chien" search to locate the symbols in error, and the error evaluator polynomial is used to calculate the values of the symbol errors. This process is inefficient when used to locate and evaluate errors in cases of less than five errors.
It is thus apparent that there is a need in the art for improved decoding methods for Reed-Solomon codes and related codes.